Tall (graf)

En teoria de grafs, un tall és una partició dels vèrtexs d'un graf en dos subconjunts disjunts. El conjunt de tall és el conjunt d'arestes que enllacen vèrtexs que estan en diferents subconjunts de la partició. Es diu que les arestes travessen el tall quan estan dins el conjunt de tall.

En un graf no dirigit i no ponderat, la mida o pes del tall és el nombre d'arestes que aquest travessa. En un graf ponderat, és la suma dels pesos de les arestes que són tallades.

En una xarxa de flux, un tall s-t és un tall en què la font i el pou estan en diferents subconjunts, i el conjunt de tall sols està compost per arestes que van des del costat de la font fins al costat del pou. La capacitat d'un tall s-t és definida per la suma de les capacitats de les arestes del conjunt de tall.

El tall d'un graf també pot referir-se al mateix conjunt de tall.